package algorithms.random.chess;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Graph {
	//private List<Node> nodes = new ArrayList<Node>(MAX_GRID_INDEX*MAX_GRID_INDEX);
	private Node[] nodeArray = new Node[SIZE*SIZE];
	private ChessPiece chessPiece = new Knight();
	private static final int SIZE=9000;
	//private static int i;
	
	private List<Node> connectedNodeList = new ArrayList<Node>(4);
	private static final int MAX_GRID_INDEX = SIZE-1;
	public Graph(){
		//init the nodes
		/*for(int i=0;i<=MAX_GRID_INDEX;i++){
			for(int j=0;j<=MAX_GRID_INDEX;j++){
				nodes.add(new Node(j,i));
			}
		}*/
		//set the adjacency list according to the carrier chess piece
		/*for(int i=0;i<=MAX_GRID_INDEX;i++){
			for(int j=0;j<=MAX_GRID_INDEX;j++){
				chessPiece.setConnectedNodes(j,i);
			}
		}*/
	}

	private Node getNode(int x, int y){
		int D1index = get1DIndex(x, y);
		Node node = nodeArray[D1index];
		if(null==node){
			//i++;
			node = new Node(x,y);
			nodeArray[D1index] = node;
		}
		return node;
	}
	public Node findShortestPath(int xSource, int ySource, int xTarget, int yTarget){
		if(xSource<0||xSource>MAX_GRID_INDEX||ySource<0||ySource>MAX_GRID_INDEX||xTarget<0||xTarget>MAX_GRID_INDEX||yTarget<0||yTarget>MAX_GRID_INDEX)
			throw new IllegalArgumentException("Coordinates outside range");
		//Standard BFS with parent links
		Queue<Node> nodeQueue = new LinkedList<Node>();
		Node sourceNode = getNode(xSource, ySource);
		sourceNode.setExplored(true);
		nodeQueue.add(sourceNode);
		Node dequedNode = null;
		Node targetNode = getNode(xTarget, yTarget);
		boolean matchFound = false;
		//int i=0;
		while(!nodeQueue.isEmpty()){
			dequedNode = nodeQueue.poll();
			//i++;
			if(dequedNode.equals(targetNode)){
				matchFound = true;
				break;
			}
			for(Node node:chessPiece.connectedNodesForNode(dequedNode)){
				if(!node.isExplored()){
					node.setParentNode(dequedNode);
					node.setExplored(true);
					nodeQueue.add(node);
				}
			}
		}
		if(!matchFound){
			dequedNode = null;
		}
		//System.out.println("i="+i);
		return dequedNode;
	}
	private void addNodeToListIfValid(int xd, int yd, List<Node> connectedNodeList){
		if(isValidNode(xd, yd)){
			connectedNodeList.add(getNode(xd,yd));				
		}
	}
	private boolean isValidNode(int m,int n){
		boolean isValidNode = false;
		if(m>=0 && n>=0 && m<=MAX_GRID_INDEX && n<=MAX_GRID_INDEX){
			isValidNode = true;
		}
		return isValidNode;
	}
	private int get1DIndex(int x,int y){
		return ((y*(MAX_GRID_INDEX+1))+x);
	}
	private class Knight implements ChessPiece {

		public List<Node> connectedNodesForNode(Node node){
			connectedNodeList = new ArrayList<Node>();
			int x = node.getX();
			int y = node.getY();
			addNodeToListIfValid(x+2, y+1, connectedNodeList);
			addNodeToListIfValid(x+2, y-1, connectedNodeList);
			addNodeToListIfValid(x-2, y+1, connectedNodeList);
			addNodeToListIfValid(x+2, y-1, connectedNodeList);
			addNodeToListIfValid(x+1, y+2, connectedNodeList);
			addNodeToListIfValid(x-1, y-2, connectedNodeList);
			addNodeToListIfValid(x+1, y-2, connectedNodeList);
			addNodeToListIfValid(x-1, y+2, connectedNodeList);
			return connectedNodeList;
		}

		

	}
	
}